package io.github.hadyang.leetcode.offer;

import java.util.PriorityQueue;
import org.junit.Test;

/** @author haoyang.shi */
public class StreamMid {

  @Test
  public void test() {
    Insert(5);
    System.out.println(GetMedian());

    Insert(2);
    System.out.println(GetMedian());

    Insert(3);
    System.out.println(GetMedian());

    Insert(4);
    System.out.println(GetMedian());

    Insert(1);
    System.out.println(GetMedian());

    Insert(6);
    System.out.println(GetMedian());

    Insert(7);
    System.out.println(GetMedian());

    Insert(0);
    System.out.println(GetMedian());

    Insert(8);
    System.out.println(GetMedian());
  }

  private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> -o1.compareTo(o2));

  private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

  private int size = 0;

  public void Insert(Integer num) {
    if (size % 2 == 0) {
      maxHeap.add(num);

      if (minHeap.isEmpty() || num > minHeap.peek()) {
        minHeap.add(maxHeap.poll());
      }

    } else {
      minHeap.add(num);

      if (maxHeap.isEmpty() || num < maxHeap.peek()) {
        maxHeap.add(minHeap.poll());
      }
    }

    size++;
  }

  public Double GetMedian() {
    if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0.0;
    if (maxHeap.isEmpty()) return minHeap.peek() * 1.0;
    if (minHeap.isEmpty()) return maxHeap.peek() * 1.0;

    if (maxHeap.size() == minHeap.size()) {
      return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }

    return maxHeap.size() > minHeap.size() ? maxHeap.peek() * 1.0 : minHeap.peek() * 1.0;
  }
}
